import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;
/*
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]
说明：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
 */
class Solution2 {

    private class Freq implements Comparable<Freq>{
        public int e; //数据
        public int freq; //词频

        public Freq(int e,int freq){
            this.e = e;
            this.freq = freq;
        }

        @Override
        public int compareTo(Freq another){
            if(freq < another.freq){
                return 1;
            }else if(freq > another.freq){
                return -1;
            }else {
                return 0;
            }
        }
    }

    public List<Integer> topKFrequent(int[] nums, int k) {
        //1、计算词频
        TreeMap<Integer,Integer> map = new TreeMap<>();
        for(int num : nums){
            if(map.containsKey(num)){
                map.put(num,map.get(num) + 1);
            }else {
                map.put(num,1);
            }
        }

        //2、创建优先队列，定义优先级（本题中应该定义最小的优先级最高）,存放目前的前K个元素
        PriorityQueue<Freq> pq = new PriorityQueue<>();
        for (int key : map.keySet()) {
            if(pq.getSize() < k){
                pq.enqueue(new Freq(key,map.get(key)));
            }else {
                if(pq.getFront().freq < map.get(key)){
                    pq.dequeue();
                    pq.enqueue(new Freq(key,map.get(key)));
                }
            }
        }

        //3.构造返回值
        LinkedList<Integer> res = new LinkedList<>();
        while (!pq.isEmpty()){
            res.add(pq.dequeue().e);
        }
        return res;
    }
}